#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>

typedef int STDataType;

typedef struct stack
{
	size_t top;
	size_t capacity;
	STDataType* a;
}ST;

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
	//初始top=0，意味着top指向栈顶元素的下一个
	//初始top=-1，意味着top指向栈顶元素
}

void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);//终止程序
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);//空栈时调用top直接终止程序报错
	ps->top--;//直接将栈顶数据删除，下一次有数据入栈会覆盖top位置
}

STDataType StackTop(ST* ps)//取栈顶元素
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;//如果top为零，说明栈中没有元素，为空
	//返回布尔值为1
}



typedef struct Queue
{
	ST L1;
	ST L2;
}MyQueue;


MyQueue* myQueueCreate() 
{
	MyQueue* Q1 = (MyQueue*)malloc(sizeof(MyQueue));
	StackInit(&Q1->L1);
	StackInit(&Q1->L2);
	return Q1;
}

void myQueuePush(MyQueue* obj, int x) 
{
	StackPush(&obj->L1, x);
}

int myQueuePop(MyQueue* obj) 
{
	if (StackEmpty(&obj->L2))
	{
		while (!StackEmpty(&obj->L1))
		{
			StackPush(&obj->L2, StackTop(&obj->L1));
			StackPop(&obj->L1);
		}
	}
	int x = StackTop(&obj->L2);
	StackPop(&obj->L2);
	return x;
}

int myQueuePeek(MyQueue* obj) 
{
	if (StackEmpty(&obj->L2))
	{
		while (!StackEmpty(&obj->L1))
		{
			StackPush(&obj->L2, StackTop(&obj->L1));
			StackPop(&obj->L1);
		}
	}
	int top=StackTop(&obj->L2);
	return top;
}

bool myQueueEmpty(MyQueue* obj) 
{
	if (obj->L1.top==0&&obj->L2.top==0)
	{
		return true;
	}
	return false;
}

void myQueueFree(MyQueue* obj) 
{
	StackDestory(&obj->L1);
	StackDestory(&obj->L2);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);

 * int param_2 = myQueuePop(obj);

 * int param_3 = myQueuePeek(obj);

 * bool param_4 = myQueueEmpty(obj);

 * myQueueFree(obj);
*/